package com.mdnote.practice.dfs_bfs;

import org.junit.Assert;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/11/10 15:18
 * @Email rhythm_2019@163.com
 * @Description 31. 下一个排列
 */
public class LeetCode31 {

    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }

        int len = nums.length;
        // 从后面往前找，找到升序部分
        int u1 = len - 2, u2 = len - 1;
        while (u1 >= 0 && nums[u1] >= nums[u2]) {
            u1--; u2--;
        }

        // 找u2右边第一个大于u1的数字
        int u3 = len - 1;
        if (u1 >= 0) {
            while (nums[u3] <= nums[u1]) {
                u3--;
            }
            // 交换u1和u3
            swap(nums, u1, u3);
        }

        // 使u1后面升序
        int left = u2, right = len - 1;
        while (left <= right){
            swap(nums, left, right);
            left++; right--;
        }
    }

    private void swap(int[] nums, int idx1, int idx2) {
        int tmp = nums[idx1];
        nums[idx1] = nums[idx2];
        nums[idx2] = tmp;
    }

    private void generate(List<Integer> nums, int level,int maxLevel, String s, List<String> resList) {
        // Terminator
        if (level == maxLevel) {
            resList.add(s);
            return;
        }

        // Process
        int size = nums.size();
        for (int i = 0; i < size; i++) {
            Integer tmp = nums.get(i);
            nums.remove(i);
            // Drill dwon
            generate(nums, level + 1, maxLevel, s + " " + tmp, resList);
            // Restore
            nums.add(i, tmp);
        }
    }

    @Test
    public void test_01() {
        LeetCode31 leetCode31 = new LeetCode31();
        int[] nums = {1, 2, 3};
        leetCode31.nextPermutation(nums);
        System.out.println(Arrays.toString(nums));
    }
}
